#ifndef __BWLIB_NUMBER_THEORY_INVERT_H__
#define __BWLIB_NUMBER_THEORY_INVERT_H__
#include "../config.h"
#include "gcd.h"
#include "module.h"
#ifdef __BWLIB_WITH_GMPXX
#include <gmpxx.h>
#endif

namespace bwlib
{
	/* @brief: 计算 a mod p 的乘法逆元，
	   		   即求解 ax = 1 (mod p)
	   @complexity: O(log n)
	   @param: a, p
	   @return: x, 0 < x < p, 
	            如果逆元不存在，返回 -1 */
	template<typename Type>
	inline Type mod_invert(const Type& a, const Type& p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		Type x, k;
		Type g = exgcd(a, p, x, k);
		if(g != 1) return Type(-1);
		return math_mod(x, p);
	}

#ifdef __BWLIB_WITH_GMPXX
	template<>
	inline mpz_class mod_invert(const mpz_class& a, const mpz_class& p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		mpz_class ans;
		if(!mpz_invert(ans.get_mpz_t(), a.get_mpz_t(), p.get_mpz_t()))
			return mpz_class(-1);
		return ans;
	}
#endif
}

#endif
